This Application is related to the following Application, which is filed of even date herewith:
xe2x80x9cMethods and Apparatuses for Performing Z-Buffer Granularity Depth Calibration in Graphics Displays of Three-Dimensional Scenes,xe2x80x9d by Richard Carl Gossweiler III and Bernardo A. Huberman, U.S. application Ser. No. 09/450,237, filed Nov. 29, 1999.
1. Field of the Invention
The present invention is related to the field of graphic rendering. Specifically, the present invention is related to the problem of selecting levels of detail for objects having multi-resolution models in complex scenes in order to reduce the graphics rendering load.
2. Discussion of the Related Art
Creating more and more detailed models, consisting of a greater number of polygons, is one way to add visual interest to a scene. However, adding polygons necessitates paying the price of having to manipulate more geometry. 3D systems have what is known as a xe2x80x98polygon budget,xe2x80x99 an approximate number of polygons that can be manipulated without unacceptable performance degradation. In general, fewer polygons yield higher frame rates.
When a rendering engine is incapable of drawing the entire scene within the allotted time frame, either the rendering engine must slow down or it must reduce the graphics complexity. Even after culling all of the objects that are not visible, the rendering engine may still not be able to draw everything within the required time frame. A fundamental technique is to reduce the graphics complexity of individual objects in the scene. If the objects have multiple resolutions, then a lower resolution object can be rendered (e.g. a lamp might be represented as a point, or a cube, or a cube with a cone or eventually as a multi-faceted polygonal model).
One aspect of this technique is determining when to transition between one level of detail (LOD) and the next. A common algorithm is to assign a distance range to each level. As the object moves further away from the viewpoint, the resolution changes. But this simple approach ignores important factors such as the cost of performing the transition, or that external parameters (such as lighting conditions, or where the object is in the view) may influence what LOD to present. A fundamental technique for reducing the graphics rendering load when displaying complex scenes is to use multi-resolution models. A common, but simplistic technique for determining when to transition from one level of detail to the next is based on the distance the object is from the viewpoint. This conventional approach frequently leads to undesirable flickering of objects and unstable frame rates.
If there are too many objects and all objects are drawn at the highest level of detail, then there may be too many objects to draw in real time, resulting in a drop in the frame rate below the desired frame rate required for smooth interactivity. For example, the desired frame rate for smooth interactivity could be fifteen frames per second. If the frame rate for a given frame falls below the desired minimum frame rate for interactivity, then the graphics renderer during the next frame may decide to draw some of the objects at lower levels of detail in an attempt to speed up the frame rate in the next frame.
Some approaches to determining levels of detail are task specific. For example, in a scene in which a pilot is attempting to land a plane on a virtual runway, then it is important to always draw the virtual runway at the highest level of detail. Some other approaches to determining levels of detail are task independent. For example, the object in the middle of the scene can always be drawn at the highest levels of detail. Flickering is the sporadic change in the rendering of an object between various levels of detail in successive frames. Flickering of an object in the periphery of a scene may draw the users attention to the flickering object and cause the user to turn the virtual camera toward the flickering object, thereby moving the flickering object into the center of the screen so that it is drawn at the higher levels of detail. Then objects previously in the center of the screen will possibly be in the periphery of the scene and may flicker, causing the user to move the camera back toward the original object. This flickering induced movement of the camera by the user in generally undesirable. Even if the flickering of objects does not alter the user""s interactive behavior with the scene, it is nonetheless visually displeasing and therefore undesirable. The flickering may additionally cause unevenness or instability in the frame rate, called hitching, which results in a staccato movement in the scene as the frame rates oscillates.
A conventional algorithm for determining the levels of detail for objects is a greedy algorithm based upon the distance from the observation point or camera. In the greedy approach, the levels of detail for the objects are determined in order of increasing distance from the observation point or camera. In other words, the closest object is drawn at the highest level of detail possible with the remaining graphics resources, and after the closest object is drawn, then the remaining graphics resources are available for the next closest object, and so on until all the graphics resources have been claimed. Other greedy approaches are based upon other measures of the relative importances of the objects instead of distances from the observation point. Greedy approaches suffer from the above-described flickering problems which may indesirably influence the visual appearance and the user""s behavior in the interactive scene. A greedy algorithm approach may still result in flickering, as the importance levels change from one object to another. To prevent this, developers are then forced to additionally include dampening functions (for example, weighting functions that retard an object from changing once it has changed).
A conventional approach for solving the above-described flickering and interactivity problems is to maintain the level of detail for an object during consecutive frames that an object is in the scene. However, this approach undesirably results in the consequence that the most important object in the scene (for example, the object in the center and/or closest to the user) is drawn at a lower level of detail if it first entered the scene at a lower level of detail.
As is apparent from the above discussion, a method is needed for determining multi-resolution model transitions in a more powerful and more general manner which can eliminate unnecessary flickering of objects and instability in the frame rate.
A fundamental technique for reducing the graphics rendering load when displaying complex scenes is to use multi-resolution models. A common, but simplistic technique for determining when to transition from one level of detail to the next is based on the distance the object is from the viewpoint. This conventional approach frequently leads to undesirable flickering of objects and unstable frame rates. According to the present invention, the portfolio method is used to provide a more powerful and more general method for determining multi-resolution model transitions which can eliminate unnecessary flickering of objects and instability in the frame rate.
According to the present invention, the level of detail selected for each object in a scene is determined based upon a variable risk parameter which may be supplied by the application. In the preferred embodiment, the risk parameter is normalized assuming values between zero and one, inclusive.
The leaf objects having levels of detail in the scene are preferably organized into a binary tree, whose structure may indicate the importance of the leaf objects. Composite parent objects each have two children objects. Children objects are either leaf objects or composite parent objects. Each composite parent object contains both of its children objects and all of the objects contained by both of its children object. The importance ranking of objects is optionally determined by one of a variety of methods. For example, the importance ranking may be predetermined based upon the type of object. Alternatively, the importance ranking is determined by decreasing order of mean hit values determined over a predetermined number of frames. As yet another alternative, the importance ranking of the objects in the scene is determined by the distances of the objects from the observation point. For example, the closest objects may be assigned the highest importance. Some combination of the above described methods for ranking the objects may also be performed in accordance with the present invention.
In a greedy algorithm embodiment, the most important object is a child of the scene object, and each composite parent object has as its two children one leaf object and one composite parent object except the deepest composition parent object which contains the least important two leaf objects. The leaf objects decrease in importance as their depth in the binary tree in this greedy embodiment.
However, the methods of the present invention are applicable to scene having any arbitrary binary tree structure. The scene object contains all leaf objects and has no parent. A recursive composite parent object process is invoked upon the two children of the scene object. In the recursive composite parent object process, graphics resources are allocated to objects A and B. A primary hit value mean corresponding to one of object A and object B is computed. In the preferred embodiment, the primary hit value mean is the average sum of hit values recorded for all the leaf objects contained by the object over a predetermined number of frames. Hit values are, for example, binary variables which take on a zero when the leaf object is not in a central portion of the scene during a frame and takes on a one if the leaf object is in the central portion of the scene during the frame. Alternatively, the hit value is a function of a static or dynamic importance weight associated with the leaf object.
According to an aspect of the present invention, the hit values for all objects contained by the other of object A and object B are summed for each of the previous predetermined number of frames to produce a secondary hit value for each of the frames. The secondary hit value mean is computed as the average of the sum of hit values for all objects contained by the other of object A and object B.
According to another aspect of the present invention, the statistical variances of the primary hit value and secondary hit value are also computed over the previous predetermined number of frames. The computation of the statistical variances of the primary and secondary hit values according to the present invention facilitates the mapping of the normalized risk parameter to a non-normalized risk parameter indicating the optimal risk for objects A and object B. The non-normalized risk parameter is substituted into a parametric variance equation. According to the present invention, the parametric variance equation is solved for the optimal fraction of the remaining graphics resources to be allocated to object A.
In the preferred embodiment, the parametric variance equation is a quadratic equation which omits a correlation term between the primary and secondary hit values. If the primary hit value mean is greater than or equal to the secondary hit value mean, the method selects the greater solution of the quadratic variance equation as the optimal fraction. Conversely, if the primary hit value mean is less than the secondary hit value mean, the method selects the lesser solution of the quadratic variance equation as the optimal fraction. The optimal fraction is multiplied by the available graphics resources, resulting in the resources allocated to object A. The available graphics resources which are not allocated to object A are allocated to object B.
According to an embodiment of the present invention, if object A is a leaf object, the level of detail is selected for object A as the level of detail associated with object A requiring the greatest amount of graphics resources not exceeding the resources allocated to object A. If object A is a composite parent object, the recursive parent object process is invoked on the two children of object A with the available graphics resources for the instantiation of the recursive parent object process set to the graphics resources allocated to object A. Similarly, if object B is a leaf object, the level of detail for object B is selected as the level of detail associated with object B requiring the greatest amount of graphics resources not exceeding the resources allocated to object B. If object B is a composite parent object, the recursive parent object process is invoked on the two children of object B with the available graphics resources for the instantiation of the recursive parent object process set to the graphics resources allocated to object B. In this manner, the total graphics resources available at the scene object is recursively divided up amongst all of the scene""s leaf nodes.
After levels of detail for all objects in the scene has been achieved, the method according to the present invention renders all leaf objects.
According to another aspect of the present invention, the non-normalized risk parameter is computed by adding the normalized risk parameter times the difference between a maximum risk and minimum risk to the minimum risk. The maximum risk is the risk associated with hit value mean having the highest value.
These and other features, aspects, and advantages of the present invention are fully described in the Detailed Description of the Invention and the Figures.